1. Field of the Invention
At earlier times IC cards have been used for some considerably specific applications, but recently, IC cards are becoming increasingly wide-spread in a variety of applications and are likely to become commonly used. It is noted that the IC cards primarily have a high degree of security.
However, provided that the IC cards are to be utilized as telephone cards, electronic money and the like, a tamper-proof mechanism is strongly required for making it difficult to forge such cards.
The present invention generally relates to a microprocessor system comprising a microprocessor and a program to be executed by the microprocessor, and, in particular, to a microprocessor system which is used in IC cards and which is randomized so as to achieve a tamper-proof property.
The present invention also relates to a method for randomizing the processor system so as to be provided with the tamper-proof property.
Also the present invention relates to an apparatus for carrying out the method.
2. Description of the Related Art
For conventional IC cards, a microprocessor embedded in the IC cards is connected to a memory such as a RAM (random access memory), ROM (read-only memory), EEPROM (electrically erasable programmable read-only memory), flash memory and the like, via an address bus and a data bus. In this case, the microprocessor is similar to a common microprocessor used in a typical microprocessor system. A program to be executed by the microprocessor is at first described using a programming language such as Fortran or C, and then compiled into executable machine codes described in the microprocessor""s machine language, using a compiler. Alternatively, the program may be described using an assembler language and then assembled into the executable machine codes described in the machine language. The executable machine codes are sequentially stored in addressable locations in the memory so as to be sequentially executed in a top-down fashion.
In this case, the machine codes are arranged within the memory in an order so as to be sequentially executed by the microprocessor. Thus, if a specification of the machine language is known, the behavior of the microprocessor can be analyzed by monitoring data stored in the memory or data transmitted on the data bus. Consequently, confidential data such as a secret key, which is used for cryptography, stored in the IC card may be taken and the secret key may be utilized to counterfeit the IC card.
Once the behavior of a microprocessor embedded in an IC card system has been analyzed and understood by outsiders, such as hackers, the outsiders may tamper with the IC card system. One approach for minimizing adverse effects caused by this tampering is to replace the current IC card system with another IC card system employing a different microprocessor from that of the current IC card system. In order to replace the current microprocessor used in the IC card system with the different microprocessor with respect to a processor type, it is required that the machine codes suited for the current microprocessor be converted into machine codes suited for the different microprocessor. Furthermore, functions realized by the current IC card system should be reproduced by the new different IC card system. That is to say, the program executed by the current microprocessor must be converted into a new program executed by the different microprocessor such that the functions realized by the current microprocessor and the current program equal those realized by the new different microprocessor and the new converted program. It has been discovered that such a new converted program cannot be easily designed in a short time interval and that, in particular, a verification of equivalence of the functions between the current microprocessor system and the different microprocessor system cannot be achieved rapidly.
FIG. 1 shows a conventional method for designing a system 10 comprising a microprocessor 20. A process for designing LSI logic such as the microprocessor will be explained with reference to FIG. 1.
First, in step 101, function designing for the LSI circuit to be designed, in this case, the microprocessor 20, is carried out in accordance with a specification of the microprocessor 20. Subsequently, function description is accomplished in step 102 and logic designing is performed in step 103. Recently, the function designing has been carried out by functionally describing the behavior of the LSI circuit with a HDL (Hardware Description Language) and verifying whether the specification requirements for the LSI circuit are satisfied by means of a function simulator.
Then, in step 104, a net list representative of gate levels is created by means of a logic combination tool on the basis of the function description for the microprocessor 20. The term xe2x80x9cnet listxe2x80x9d is such that it describes a connectivity relation among cells which have a simple logical operation, such as NAND or NOR gates or a flip-flop, and which are included in a cell library. Once the net list has been created, a logic simulation for the microprocessor 20 is performed with the net list and a library for delay elements, and the behavior of the microprocessor 20 is verified. Thereafter, in step 105, layout designing for the microprocessor 20 is carried out using an place and route tool on the basis of the net list, and a mask pattern for the microprocessor 20 is created in step 106. Finally, in step 107, a mask is made in accordance with data derived from the mask pattern and the microprocessor 20 is produced.
The microprocessor system 10 comprising the microprocessor 20 further includes a program 40 to be executed by the microprocessor 20. In step 111, a source program is described with a high-level language such as Fortran or C. In step 112, the described source program is compiled or assembled into a sequence of machine codes, hereinafter also referred to as a xe2x80x9cmachine code program 40,xe2x80x9d which can be executed by the microprocessor 20. The microprocessor system 10 further includes a memory for storing the machine code program therein.
Thus, the microprocessor system 10 has the microprocessor 20 and the machine code program 40 being developed and manufactured according to the above-mentioned steps. In general, the microprocessor 20 and the memory 30 are connected via data and address buses. The machine code program 40 is downloaded into the memory 30 by a loader program and the like, or previously is written into the memory 30. The microprocessor 20 has an access to the memory 30 so as to execute instructions from the machine code program 40 and achieve the functions of the microprocessor system 10 appropriately.
For each type of the microprocessors, it is noted that there is a single set of the function description, the net list and the mask pattern. Also, the compilation of the source program written with the single high-level language will result in a unique machine code program.
An example of such a microprocessor system is an IC card system that has recently come into common use. In the case of the IC card system, a plurality of IC cards of the same type are issued as a group and each IC card belonging to the same group has the same functionality. Each IC card includes an equivalent microprocessor 20 and an equivalent machine code program 40. It is assumed that one of the IC cards from the group is analyzed by the outsiders with respect to a logical architecture of the microprocessor 20 as well as the machine code program 40 in the memory 30. As a result, the other IC cards belonging to the same group as said analyzed IC card are subject to a high risk of being tampered with by the outsiders.
Once it is discovered that the logical architecture of the microprocessor 20 and the machine code program 40 stored in the memory 30 have been analyzed by the outsiders, measures should be taken in order to prevent the IC card system from being tampered with by the outsiders. To do this, the current microprocessor system 10 including the current microprocessor 20 may be replaced with a new microprocessor system including a different microprocessor from that of the current system. In this case, a new source program corresponding to the new microprocessor must be developed. This new source program is edited and compiled in accordance with requirements such that the resultant new machine code program from the source program serves the same functionality as that for the original microprocessor. However, as previously stated, a long time is required to design and develop such a new source program satisfying the requirements. Furthermore, the newly designed and developed program may include some bugs. Thus, it has been discovered that it is considerably difficult to develop the new program in order to protect the IC card system from being tampered with by the outsiders.
In the above-mentioned microprocessor system such as the IC card system comprising the microprocessor and the program capable of being executed by the microprocessor, the known method for protecting the system from being tampered with by the outsiders consists of replacing the current system with the newly developed system. However, this approach has a first disadvantage in that it is difficult to rapidly modify the microprocessor architecture and the program to be executed by the modified microprocessor while ensuring that an equivalence of the functionality is maintained between the current system and the modified system.
Now, a conventional microprocessor unit MPU will be explained with reference to FIG. 2. The MPU 20 comprises a data path 50 and a control unit 60. Such a type of MPU is described, for example, in xe2x80x9cULSI Design Technology,xe2x80x9d page 114, FIG. 5.2, The Institute Of Electronics, Information and Communication Engineers, edited by Shoji Horiguchi.
The data path 50 includes an arithmetic logical unit (ALU) 51, a general purpose register 52, a program counter 53, an instruction register 54 and a bus interface 55. The control unit 60 includes an instruction decoder 61 and a micro-program control circuit 62. The MPU 20 is connected to an external memory 30, such as a RAM or ROM, via the bus interface 55, an external address bus 71 and an external data bus 72.
FIG. 3 illustrates, as an example, a program stored in the memory 30 of the MPU 20 within the conventional microprocessor system. The memory 30 has opcodes op1, op2, . . . , op8 stored therein at corresponding addresses 0000, 0001, . . . , 0111, respectively. In this case, for the clearness of the drawing, addresses more than 0111 have not been depicted, but opcodes are also stored in the memory 30 at addresses over 0111. In other words, each of the predetermined opcodes is stored in the memory 30 at the corresponding assigned address. It should be noted that an order of the opcodes stored in the memory 30 corresponds to an order for executing instructions corresponding to the opcodes. For example, the opcodes stored in the memory 30 are sequentially executed as the address at which the opcode is stored increases.
In the conventional MPU 20, a value set in the program counter 53 is supplied to the external bus address 71. The memory 30 provides a content at the address specified by the external address bus 71 to the external data bus 72. The content from the memory 30 is transferred to an internal bus 56 of the MPU 20 via the bus interface 55, and then is latched into the instruction register 54. The content, i.e., opcodes, latched into the instruction register 54 is decoded in the instruction decoder 61, which passes the decoded opcodes to the micro-program control circuit 62 in the control unit 60. The micro-program control circuit 62 generates various signals and executes the instructions in accordance with the opcodes.
Supposed that an instruction stored in the memory 30 at the address corresponding to the value set in the program counter 53 is executed. If the executed instruction is a normal instruction excluding a jump instruction, then the value of the program counter 53 is incremented. Subsequently, the content of the memory 30 at the address corresponding to the value of the program counter 53 is read from the memory 30 and the process for executing the instruction is repeated.
FIG. 4 shows a diagram of the program counter 53. The program counter comprises a register 81 and an increment unit 82 for increasing an output value from the register 81 by +1. In response to a predetermined clock, the register 81 has a given value. The increment unit 82 increments the value in the register 81 and generates the incremented value. At a next clock following the predetermined clock, the register 81 is set to the incremented value by the increment unit 82. This process is continued in response to the following clocks.
In this case, it is assumed that the program counter 53 has been initially set to 0. Then, the opcode xe2x80x9cop1xe2x80x9d is read from the memory 30 at the address xe2x80x9c0000,xe2x80x9d which address corresponds to the value set in the program counter 53. The opcode xe2x80x9cop1xe2x80x9d is executed as earlier described. The content of the program counter 53 is further incremented and the incremented value is provided to the memory 30 as the address specifying a location where the opcode to be read is stored. Thus, the opcode xe2x80x9cop2xe2x80x9d stored in the memory 30 at the address xe2x80x9c0001xe2x80x9d is read from the memory and executed. Then, the opcodes op3, op4, . . . , op8 are sequentially read from the memory and executed.
FIG. 5 shows a diagram of the micro-program control circuit 62 in the MPU 20 as shown in FIG. 2. The micro-program control circuit 62 comprises a xcexc-program (micro-program) counter 91, a xcexc-program memory 92 and a xcexc-instruction decoder 93. The content set in the instruction register 54 (FIG. 2) is decoded in the instruction decoder 61 of the control unit 60, and thereafter the decoded content is set to the xcexc-program counter 91 as a xcexc-instruction stored address. A xcexc-instruction is retrieved from the xcexc-program memory 92 at the address represented by the xcexc-program counter 91, and then decoded in the xcexc-program instruction decoder 93. As a result, control signals are transferred from the control unit 60 to the data path 50 so as to execute the instruction.
After executing the instruction, the content of the xcexc-program counter 91 is incremented. Then the xcexc-instruction is again retrieved from the xcexc-program memory 92 at the address represented by the xcexc-program counter 91, decoded in the xcexc-program instruction decoder 93 and executed by transferring the control signals from the control unit 60 to the data path 50.
In the above-mentioned conventional MPU 20, the content of the program counter is incremented by +1. Since the output value from the program counter 53 is used to address the location where the opcode in the program to be executed is retrieved, the opcode in the program should be sequentially stored in the memory 30 in the same order as the opcode is executed.
As can be understood from the above description, the conventional approach has a second disadvantage as follows. When each opcode in the program 40 is sequentially stored in the memory 30 in the same order as the opcode is executed, the program 40 stored in the memory 30 may be analyzed by sequentially retrieving the data stored in a memory cell of the memory 30.
In addition, the program 40 stored in the memory 30 is transferred from the memory 30 to the MPU 20 via the data bus 72. This allows for outsiders to recognize the program 40 stored in the memory 30 by monitoring the data transmitted on the data bus 72 rather than by directly retrieving the data from the memory 30. This causes a third disadvantage of the known approach in that the outsiders may easily analyze the behavior of the MPU 20.
The above-mentioned conventional method has the disadvantage that the opcodes in the program 40 stored in the memory 30 are sequentially executed. On the contrary, a jump instruction according to the prior art is not always executed sequentially. FIG. 6 shows a diagram of a conventional program counter 53a adapted to the jump instruction. As shown in FIG. 6, the program counter 53a comprises the register 81, the increment unit 82 for increasing the content of the register 81 by 1 and a selector 83. The selector 83 is provided for changing between an output signal from the increment unit 82 and an address output from the control unit 60 as the address to be jumped to for the next instruction.
When the MPU 20 is operative for a normal instruction rather than the jump instruction, in response to the predetermined clock, the register 81 in the program counter 53a is set to 0000. The increment unit 82 adds 1 to the content of the register 81 and outputs the summed value to the selector 83. The selector 83 receives the output signal from the increment unit 82 at a first input thereof and, in this case, selects the output signal from the increment unit 82 as the value to be set to the register 81 at the next clock. Thus, as the value of the address to be set to the program counter 53a is increased, these steps for advancing the program counter 53a are repeated.
Here is the operation of the program counter 53a when the jump instruction is given. The jump instruction is the instruction that changes the order of the opcode to be executed.
In the following description, the instruction xe2x80x9cJPxe2x80x9d indicates an opcode for an unconditional jump instruction whose operand directly specifies an address to be jumped to. For example, the instruction xe2x80x9cJP1000xe2x80x9d indicates that the opcode is equal to xe2x80x9cJPxe2x80x9d and the operand is equal to xe2x80x9c1000.xe2x80x9d On one hand, since the instruction xe2x80x9cJP1000xe2x80x9d states that the value of the program counter 53a is set to be equal to xe2x80x9c1000,xe2x80x9d the content stored in the memory 30 at the address 1000 is retrieved from the memory 30 and the content representing an instruction is executed. On the other hand, in terms of the memory 30, the operand xe2x80x9c1000xe2x80x9d is stored at the address directly succeeding the address where the opcode xe2x80x9cJPxe2x80x9d is stored.
It will be easily understood by those skilled in the art that the above-mentioned jump instruction xe2x80x9cJPxe2x80x9d generally represents the unconditional jump instruction but is not intended to be executed by only a particular microprocessor. Therefore, the unconditional jump instruction of interest is not limited to the particular xe2x80x9cJPxe2x80x9d instruction defined beforehand and may be principally expanded to various jump instructions which can be defined for the different existing microprocessors commercially available in the market.
FIG. 7 shows an example of the program 40 contained in the memory 30, which program 40 includes the unconditional jump instruction. The operation of the conventional MPU 20 that is provided with the program counter 53a when the MPU 20 runs the program including the unconditional jump instructions will now be explained.
At first, the register 81 of the program counter 53a is initially set to xe2x80x9c0000.xe2x80x9d This allows the MPU 20 to read the opcode xe2x80x9cop1xe2x80x9d stored in the memory 30 at the address xe2x80x9c0000xe2x80x9d and execute the opcode xe2x80x9cop1.xe2x80x9d Then, the increment unit 82 increments the address stored in the register 81 of the program counter 53a by 1. As the program counter 53a is incremented, the opcodes xe2x80x9cop2xe2x80x9d and xe2x80x9cop3xe2x80x9d stored in the memory 30 are sequentially read out from the memory 30 at the respective incremented addresses. Thereafter, the register 81 of the program counter 53a is set to the value equal to xe2x80x9c0011,xe2x80x9d and the MPU 20 retrieves the opcode xe2x80x9cJPxe2x80x9d from the memory 30 at the address of xe2x80x9c0011.xe2x80x9d After the jump instruction xe2x80x9cJPxe2x80x9d has been taken, the MPU 20 generates the address xe2x80x9c0100,xe2x80x9d which corresponds to the next address to be retrieved, to the address bus 71. In this manner, the content having the value of xe2x80x9c1000xe2x80x9d in the memory 30 at the address xe2x80x9c0100xe2x80x9d is retrieved from the memory 30. Since this value xe2x80x9c1000xe2x80x9d contained in the memory 30 corresponds to the address to be jumped to for the jump instruction, the selector 83 of the program counter 53a selects another input for receiving the jump address xe2x80x9c1000.xe2x80x9d
The MPU 20 provides the value xe2x80x9c1000xe2x80x9d set in the register 81 to the address bus 71, retrieves the instruction xe2x80x9cop9xe2x80x9d stored in the memory 30 at the address xe2x80x9c1000xe2x80x9d and executes the instruction xe2x80x9cop9.xe2x80x9d At the same time, the increment unit 82 of the program counter 53a generates a sum of the content of the register 81 and the value xe2x80x9c1.xe2x80x9d The resultant sum calculated by adding xe2x80x9c1xe2x80x9d to the content xe2x80x9c1000xe2x80x9d is equal to xe2x80x9c1001.xe2x80x9d The control unit 60 determines that the present instruction xe2x80x9cop9xe2x80x9d is not the jump instruction. Then the selector 83 selects the first input receiving the output xe2x80x9c1001xe2x80x9d from the increment unit 82 and sets this value to the register 81. Until the instruction to be executed is equal to the jump instruction, the selector 83 continues to receive the output signal from the increment unit 82 at the first input and set the value corresponding to the received signal from the increment unit 82 to the register 81.
The addresses generated by the program counter 53a are xe2x80x9c0000,xe2x80x9d xe2x80x9c0001,xe2x80x9d xe2x80x9c0010,xe2x80x9d xe2x80x9c0011,xe2x80x9d xe2x80x9c1000,xe2x80x9d xe2x80x9c1001,xe2x80x9d xe2x80x9c1010,xe2x80x9d xe2x80x9c1011,xe2x80x9d xe2x80x9c1100,xe2x80x9d xe2x80x9c1101xe2x80x9d and xe2x80x9c1110,xe2x80x9d as shown in FIG. 6. It should be noted that the jump instruction included in the program causes the address xe2x80x9c0011xe2x80x9d to be followed by the address xe2x80x9c1000.xe2x80x9d
In addition to the unconditional jump instruction xe2x80x9cJP,xe2x80x9d a relative jump instruction xe2x80x9cJR,xe2x80x9d which is another type of the jump instruction, will be explained. The relative jump instruction xe2x80x9cJRxe2x80x9d is defined as a jump instruction that adds a certain value to the current value of the program counter 53a and takes the resultant value as the address to be jumped to. The relative jump instruction comprises the opcode xe2x80x9cJRxe2x80x9d and the operand representative of said certain value to be added to the current value of the program counter 53a. The operand, for example, corresponds to the difference between the top address of the xe2x80x9cJRxe2x80x9d instruction and the address to be jumped to. In particular, as an example, the address to be jumped to (it is also called xe2x80x9cjump addressxe2x80x9d hereinafter) is written as follows:
JUMP ADDRESS=ADDRESS OF OPCODE xe2x80x9cJRxe2x80x9d+ASSOCIATED OPERAND+1
The operand for the relative jump instruction is stored in the memory 30 at the address next to that of the location where the opcode xe2x80x9cJRxe2x80x9d for the relative jump instruction is stored. For example, the instruction xe2x80x9cJR0011xe2x80x9d indicates that the relative jump is to be made to the jump address equal to the value of the current program counter 53a value +the operand xe2x80x9c0011xe2x80x9d+1.
It will be easily understood by those skilled in the art that the above-mentioned relative jump instruction xe2x80x9cJRxe2x80x9d generally represents the relative jump instruction but is not intended to be executed only by a particular microprocessor. Therefore, the relative jump instruction of interest is not limited to the particular xe2x80x9cJRxe2x80x9d instruction defined beforehand and may be principally expanded to various jump instructions which can be defined for the different existing microprocessors commercially available in the market.
FIG. 8 shows an example of the program 40 contained in the memory 30, which program 40 includes the relative jump instruction. The operation of the conventional MPU 20 that is provided with the program counter 53a when the MPU 20 runs the program including the relative jump instructions will now be explained.
The MPU 20 loads the contents stored in the memory 30 thereto starting from the address xe2x80x9c0000xe2x80x9d of the memory 30 and executes the instructions corresponding to the contents loaded from the memory 30. It is assumed that the opcode xe2x80x9cJRxe2x80x9d stored in the memory 30 at the address of xe2x80x9c1011,xe2x80x9d as shown in FIG. 8, is reached and loaded into the MPU 20. Then the MPU 20 decodes the opcode xe2x80x9cJRxe2x80x9d and reads the content of the memory at the address next to the address xe2x80x9c1011xe2x80x9d where the opcode xe2x80x9cJRxe2x80x9d is stored. That is to say, the value xe2x80x9c0010xe2x80x9d stored in the memory 30 at the address xe2x80x9c1100xe2x80x9d is read from the memory. Then the jump address is calculated according to the above-mentioned formulation, such that:
The jump address=address xe2x80x9c1011xe2x80x9d+0010+1=1110
The resultant jump address is set via the selector 83 of the program counter 53a to the register 81 as the address where the next instruction to be executed is stored.
Subsequently, the MPU 20 provides the address xe2x80x9c1110xe2x80x9d held in the register 81 to the address bus 71, retrieves the instruction from the memory 30 at the address xe2x80x9c1110xe2x80x9d and executes the retrieved instruction. Thus, in this case, the program counter 53a generates the addresses, which specify the locations in the memory 30 where the instruction are to be read from and executed, in a sequence of xe2x80x9c0000,xe2x80x9d xe2x80x9c0001,xe2x80x9d xe2x80x9c0010,xe2x80x9d xe2x80x9c0011,xe2x80x9d xe2x80x9c0100,xe2x80x9d xe2x80x9c0101,xe2x80x9d xe2x80x9c0110,xe2x80x9d xe2x80x9c0111,xe2x80x9d xe2x80x9c1000,xe2x80x9d xe2x80x9c1001,xe2x80x9d xe2x80x9c1010,xe2x80x9d xe2x80x9c1011xe2x80x9d and xe2x80x9c1110.xe2x80x9d It should be noted that the relative jump instruction xe2x80x9cJRxe2x80x9d causes the address xe2x80x9c1110xe2x80x9d to occur following the address xe2x80x9c1011.xe2x80x9d
As described above, in the conventional microprocessor system, if the instruction to be executed is an instruction other than the jump instruction, then the program counter 53a value is incremented by +1 and the opcode stored in the memory 30 is sequentially taken and executed. However, if the instruction to be executed is the jump instruction, the operand following the jump opcode is taken as a further address specifying the location of the memory 30 from which the content should be read. In the case of the unconditional jump, the content read from the memory 30 is directly taken as the instruction to be executed and then is executed by the MPU 20. In the case of the relative jump, the content is taken as a further address representing the above-mentioned difference between the jump address and the current address and is used to calculate the jump address.
In the above-mentioned conventional microprocessor, since each code of the program is sequentially ordered in the memory, a particular mechanism is provided for appropriate execution of the jump instructions. The inventors have discovered that it would be effective to randomize the order of the codes of the program arranged in the memory in order to make the understanding of the program difficult, even if the program has been read by outsiders. However, the conventional microprocessor system has a fourth disadvantage in that the jump instruction cannot be appropriately executed when the order of the program codes stored in the memory is randomized. Thus, a new mechanism for executing the jump instruction is required when the order of the program codes stored in the memory is randomized.
FIG. 9 shows a schematic diagram of a conventional microprocessor system. For convenience of the description, an 8-bit type of microprocessor, i.e., a Z-80 microprocessor, is assumed as an example of a microprocessor used in the conventional microprocessor system. Of course, the following description applies to various microprocessors having a bus width more than 8 bits.
The microprocessor system 10 comprises the microprocessor 20 and the memory 30, as shown in FIG. 9. An address bus terminal 73 of the microprocessor 20 is connected to an address bus terminal 75 of the memory 30 via an address bus 71. Also, a data bus terminal 74 of the microprocessor 20 is also connected to a data bus terminal 76 of the memory 30 via a data bus 72.
FIG. 10 shows a connection between the data bus terminal 74 of the microprocessor 20 and the data bus terminal 76 of the memory 30 in the microprocessor system 10 as shown in FIG. 9. A line D7 for a MSB (most significant bit) of the data bus 72 at the microprocessor 20 is connected to a further line D7 for the MSB of the data bus 72 at the memory 30. Also lines D6, D5, . . . , D1 and D0 at the microprocessor 20 are connected to lines D6, D5, . . . , D1 and D0 at the memory 30, respectively. In this case, concerning an order of assigned bit numbers, the lines D7, D6, . . . , D1 and D0 at the microprocessor 20 correspond to the lines D7, D6, . . . , D1 and D0 at the memory 30, respectively.
FIG. 11 shows an example of a structure of the memory 30 in which the program to be executed by the microprocessor 20 is stored. In this case, the program codes applicable to the Z-80 microprocessor are illustrated, but the same explanation can be applied to any type of microprocessor other than the Z-80 microprocessor. The memory 30 contains codes of 31(H) (in hexadecimal notation) or 00110001(B) (in binary notation) at the address 0, FF(H) at the address 1, 7F(H) at the address 2, 06(H) at the address 3, and so on, in sequence. These codes are represented in a machine language for the Z-80 microprocessor as follows:
LD SP, 7FFF; load 7FFF into SP
LD B, 11; load 11 into register B
When the microprocessor 20 is reset by a reset signal and then is released from a reset status, the microprocessor 20 delivers the signal representing the address 0 to the address bus 71. The content value of 31(H) from the memory 30 at the address 0 specified by the address bus 71 is transferred to the MPU 20. Then the MPU 20 decodes the transferred value and takes xe2x80x9cLDxe2x80x9d as an opcode for the instruction. The MPU 20 attempts to take the operand/operands for the decoded instruction. In this case, since the opcode xe2x80x9cLDxe2x80x9d is provided with two operands, the MPU 20 delivers the address 1 and the subsequent address 2 to the address bus 71 in order to retrieve two operands from the memory 30 at the designated addresses. As a result, the contents FF(H) and 7F(H) from the memory 30 at the addresses 1 and 2, respectively, are delivered to the MPU 20.
Thus, the MPU 20 can translate the contents sequentially read from the memory 30 to the appropriate instruction xe2x80x9cLD SP, 7FFF,xe2x80x9d which causes the MPU 20 to load a value of 7FFF into a stack pointer SP. After the execution of this instruction xe2x80x9cLD SP, 7FFF,xe2x80x9d the MPU 20 delivers the value representing the address 3 to the address bus 71 in order to read the content from the memory 30 at the address 3. As a result, the MPU 20 can read the content xe2x80x9c06xe2x80x9d from the memory at the address 3. Thereafter, the MPU 20 sequentially delivers the subsequent address to the memory 30 via the address bus 71, reads the content from the memory 30 at the delivered address via the data bus 72, decodes the content and executes the decoded content representing a respective instruction.
As previously mentioned, in the conventional microprocessor system 10, the microprocessor 20 sequentially reads the content from the memory 30 at the respective specified address, decodes and interprets the content, and executes the instruction corresponding to the content. The machine codes of the program stored in the memory 30 are arranged in an order to be executed by the microprocessor 20. The memory 30 contains an opcode for each step of the program at the address corresponding to the order to be executed. It should also be noted that each bit of the opcode is assigned directly, i.e., without exchanging a bit position, to the same bit in the memory 30 at the corresponding address. Thus, a MSB of the opcode corresponds to a MSB in the memory 30, a bit 6 of the opcode corresponds to a bit 6 in the memory 30, and so on. That is to say, a bit x (x represents an integer ranging from 0 to 7) of the opcode is stored in the bit x of memory 30 at a corresponding address.
As can be understood from the above description, in the conventional microprocessor system 10, each opcode in the program 40 is sequentially stored in the memory 30 in the same order as the opcode is executed. Furthermore, each bit of the opcode is assigned to the same bit of the memory 30 at the address at which the opcode is stored. This makes it possible for outsiders to easily analyze and understand the program stored in the memory 30 by reading the contents from memory cells in the memory 30. In addition, the program 40 stored in the memory 30 is transferred from the memory 30 to the MPU 20 via the data bus 72. This allows for the outsiders to recognize the program 40 stored in the memory 30 by monitoring the data transmitted on the data bus 72 rather than by directly retrieving the data from the memory 30. This causes a fifth disadvantage of the known approach as follows. The outsiders may easily analyze the behavior of the microprocessor system 10 when the memory 30 stores data into its memory cell while keeping a bit order of the data in the same order as transmitted on the data bus 72.
FIG. 12 shows a diagram of an LSI circuit used in a conventional IC card, the LSI circuit comprising an MPU, an EEPROM, a RAM, and a ROM. In general, these elements are arranged on a single chip and the LSI circuit further includes a bus area, which bus area connects wires between these elements.
FIG. 13 illustrates an example of a layout of buses according to the prior art. As shown in FIG. 13, the layout is provided with a circuit 100, such as a memory, bus lines 101, 102, . . . , 108, bus lines in columns 111, 112, . . . , 118, bus lines in rows 121, 122, . . . , 128, and through holes A and B. In this case, a count of these bus lines corresponds to a count of bits comprising data to be transmitted via these buses. Hereinafter, a set of 8 bus lines is also referred to as a xe2x80x9cbus-line group.xe2x80x9d In the conventional LSI circuit, as shown in FIG. 13, a bus-line group in columns and a bus-line group in rows are formed on separate interconnection layers. For example, it is assumed that a number of the interconnection layers amounts to 4. In this case, the bus-line group in columns, i.e., the bus lines in columns 111, 112, . . . , 118, is divided so as to be assigned to second and fourth interconnection layers, and the bus-line group in rows, i.e., the bus lines 121, 122, . . . , 128, is divided so as to be assigned to first and third interconnection layers. The through holes serve to connect the bus lines in columns and the bus lines in rows between the different interconnect layers. Now, it is assumed that a particular layout achieving an interconnection with a given number of bits is designed. Each bus line assigned to a respective one of the bits is arranged on an interconnection layer such that the bit number corresponding to the bus line is aligned in sequence in order to effectively perform the layout.
As shown in FIG. 13, the bus-line group in columns is arranged on the second interconnection layer and the bus-line group in rows is arranged on the first interconnection layer. On one hand, at a bottom-right part of the drawing, terminals for bits 0, 1, . . . , 8 of a circuit (not shown) are connected to the bus lines 128, 127, . . . , 121, respectively, on the first interconnection layer. The bus lines 128, 127, . . . , 121 are extended in a row direction and reach to the through holes B. The bus lines in rows 128, 127, . . . , 121 are connected to the bus lines in columns 118, 117, . . . , 111 on the second interconnection layer, respectively, via the thorough holes B. On the other hand, terminals bit 7, bit 6, . . . , bit 0 at the circuit 100 are connected to the bus lines in rows 101, 102, . . . , 108, respectively. Furthermore, the bus lines 101, 102 . . . 108 are connected to the bus lines 111, 112, . . . , 118, respectively, via the through holes A.
As a result of the above-mentioned layout, the bus lines in rows 128, 127, . . . , 121 on the first interconnection layer are arranged in sequence such that the bit number increases as the line number decreases. Also, the bus lines in columns 118, 117, . . . , 111 on the second interconnection layer are arranged in sequence such that the bit number increases as the bus line number decreases.
As IC cards are becoming increasingly wide-spread in a variety of applications, it is more important to protect an IC card system from being tampered with. On one hand, signals transmitted on wiring lines within the IC card can be analyzed by means of a fault analysis tool for an LSI circuit. On the other hand, important information, such as a secret key for cryptography, stored in the IC card, is transferred between a microprocessor and various memories via bus lines connecting the microprocessor to the memories. As a result, the important information may be read from the bus lines using the fault analysis system, so that the IC cards may be subject to a risk of being forged. This causes a problem that a level of a security for the IC card system is degraded. Another tool, such as a manual probe unit may be used to read various confidential data from the bus lines.
In the conventional layout of the buses, as shown in FIG. 13, the bus lines are arranged in sequence in terms of the bit number. Therefore, the information transmitted on the bus lines can be easily reconstructed using data picked up from the bus lines bit by bit. Furthermore, if a bus-line group is arranged on a single interconnection layer, the data transmitted on each bus line of the bus-line group can be easily picked up as a whole by directly probing the bus lines. Thus, the conventional layout of the buses has a sixth disadvantage in that the information transmitted on the bus lines may be easily read and determined, so that a behavior of a microprocessor system formed using that layout may be analyzed.
It is a first object of the present invention to overcome the above-mentioned first disadvantage of the prior art. One aspect of the first object of the present invention relates to a method for randomizing a microprocessor system including a microprocessor and a program executable by the microprocessor, an apparatus for carrying out the method and a randomized microprocessor system. It is assumed that a current microprocessor system comprising a current microprocessor and a current program is provided. The present invention is based on the fact that a further microprocessor system comprising a further microprocessor different from the current microprocessor and a further program different from the current program is generated by randomizing the current microprocessor system while achieving a functionality equivalent to that of the current microprocessor system.
In the context of the present invention, to xe2x80x9crandomizexe2x80x9d a microprocessor system means to randomize a microprocessor and a program included in the microprocessor system while maintaining an equivalence of functionality realized by the microprocessor system regardless of this randomization.
The above first object of the present invention is achieved by a microprocessor system including a microprocessor and a memory storing items accessible to the microprocessor, the microprocessor system comprising:
means for randomizing the items stored in the memory, and
means for randomizing the microprocessor so as to allow the microprocessor to have an access to the randomized items stored in the memory.
In another aspect of the present invention, the above first object is achieved by a method for randomizing a microprocessor system including a microprocessor and a memory storing items accessible to the microprocessor, the microprocessor system performing a given functionality, the method comprising steps of:
(a) randomizing the items stored in the memory in accordance with randomizing information, and
(b) randomizing the microprocessor so as to allow the microprocessor to have an access to the randomized items stored in the memory,
whereby a randomized microprocessor system performing a functionality equivalent to the given functionality is generated.
The method for randomizing a microprocessor system may further comprise the steps of:
for each randomizing information, repeating the steps (a) and (b),
whereby the microprocessor system is separately randomized repeatedly such that separate microprocessor systems realizing an equivalent functionality are generated.
In a further aspect of the present invention, an apparatus for carrying out the above-mentioned method achieves the above first object. According to the present invention, the apparatus for randomizing a microprocessor system including a microprocessor and a memory storing items accessible to the microprocessor, the microprocessor system realizing a given functionality, comprises:
first randomization means for randomizing the items stored in the memory in accordance with randomizing information, and
second randomization means for randomizing the microprocessor so as to allow the microprocessor to have an access to the randomized items stored in the memory,
whereby a randomized microprocessor system realizing a functionality equivalent to the given functionality is generated.
The apparatus for randomizing a microprocessor system is characterized in that the randomizing information consists of a first key used for randomizing the items in the first randomization means and a second key used for randomizing the microprocessor in the second randomization means, and that the first key and the second key are correspondingly selected such that the randomized microprocessor system is capable of realizing the functionality equivalent to the given functionality. Thus, an appropriate selection of the first key and the second key enables an easy tamper-proof action for prohibiting an unauthorized analysis of the microprocessor system.
As previously mentioned, according to the present invention, in an original microprocessor system including a current microprocessor and a current program executable by the microprocessor, a further microprocessor different from the microprocessor and a further program different from the current program are generated by randomizing the current program and the current program, respectively. The further microprocessor realizes a functionality equivalent to that of the current microprocessor and the further program is executable by the further microprocessor. It is noted that the current microprocessor and the current program are randomized based on the same randomizing rule. Thus, a randomized microprocessor system including the further microprocessor and the further program can realize the same functionality as that of the original microprocessor.
Therefore, the present invention has an advantage that a new system having an equivalent functionality to that of the current system can be generated more rapidly and at a lower cost by modifying the microprocessor and the program in a short time, in spite of differences in hardware and software between the new system and the current system.
It is a second object of the present invention to overcome the above-mentioned second disadvantage of the prior art. One aspect of the second object of the present invention relates to a method for randomizing a microprocessor system including a microprocessor and a memory storing a program executable by the microprocessor, in that the program is stored in the memory such that the program cannot be understood by reading the program from the memory in sequence. Another aspect of the second object of the present invention relates to an apparatus for carrying out the above method. A further aspect of the second object of the present invention relates to a randomized microprocessor system.
The second object of the present invention is achieved by a microprocessor system including a microprocessor and a memory storing a program executable by the microprocessor, the microprocessor system realizing a given functionality, the microprocessor system comprising:
means for randomizing addresses according to randomizing information, codes of the program stored in the memory at the addresses being accessible by the microprocessor,
wherein the memory stores the codes of the program at the randomized addresses.
The second object of the present invention is also achieved by a microprocessor system including a microprocessor and a memory storing codes of a program executable by the microprocessor, the microprocessor system realizing a given functionality, the microprocessor system comprising:
a pseudo-random pattern generator for generating a random sequence other than a sequence having numbers sequentially increasing, and
program reading means for determining each address at which each code of the program is read from the memory based on the random sequence generated by the pseudo-random pattern generator and for reading the code from the memory at the determined address.
In the microprocessor system according to the present invention, the codes of the program are stored in the memory at the addresses specified by the random sequence. Therefore, the program cannot be appreciated as a correct series of the codes when the codes stored in the memory are read at the addresses in a sequential order. Advantageously, this makes it difficult for outsiders to analyze and understand the program correctly.
It is a third object of the present invention to overcome the above-mentioned third disadvantage of the prior art. One aspect of the third object of the present invention relates to a method for randomizing a microprocessor system including a microprocessor and a memory storing a program executable by the microprocessor. The microprocessor system is randomized such that it is difficult to analyze and understand the program stored in the memory, and, thus, a behavior of the microprocessor. Another aspect of the third object of the present invention relates to an apparatus for carrying out the above method. A further aspect of the third object of the present invention relates to a randomized microprocessor system.
The above third object of the present invention is achieved by a microprocessor system including a microprocessor and a memory storing items accessible to the microprocessor. The microprocessor system comprises:
means for converting a first address generated in the microprocessor into a second address in accordance with a given rule, and
means for having an access to the memory at the second address.
In the microprocessor system according to the present invention, each opcode to be executed by the microprocessor is stored in the memory at the second address different from the first address at which the microprocessor considers the opcode is stored. As a result, since the opcodes stored in the memory are arranged in a randomized order, the microprocessor can not appropriately read and execute the opcodes in the memory. Therefore, it is difficult for outsiders to analyze and understand a behavior of the microprocessor system by directly reading the opcodes or contents stored in the memory. Advantageously, this improves a security for the microprocessor system, in particular, an IC card system.
It is a fourth object of the present invention to overcome the above-mentioned fourth disadvantage of the prior art. One aspect of the fourth object of the present invention relates to a microprocessor system whose program counter includes a pseudo-random pattern generator, in particular, such as an LFSR (Linear Feedback Shift Register). The microprocessor system has to be able to generate a correct jump address when a jump instruction is to be executed.
The above fourth object of the present invention is achieved by a microprocessor system including a microprocessor and a memory storing a program executable by the microprocessor. The microprocessor system comprises:
a pseudo-random pattern generator for generating a random sequence other than a sequence having numbers sequentially increasing;
program reading means for randomizing each address of the memory based on the random sequence generated by the pseudo-random pattern generator and for reading each code of the program from the memory at the randomized address;
jump address memory means for storing address information corresponding to a jump address for a jump instruction, the address information being represented by the randomized address, and
means having an access to the jump address memory means and retrieving the jump address information from the jump address memory means in response to the code of the program read from the memory being the jump instruction.
In the microprocessor system according to the present invention, it is advantageous that the microprocessor system can generate a correct jump address for a jump instruction while a program counter of a microprocessor comprises a pseudo-random pattern generator such as an LFSR.
It is a fifth object of the present invention to overcome the above-mentioned fifth disadvantage of the prior art. One aspect of the fifth object of the present invention relates to a method for randomizing a microprocessor system including a microprocessor and a memory storing a program executable by the microprocessor. The microprocessor system is randomized by exchanging an order of a bit alignment on a path from the microprocessor to the memory in order to make it difficult to read and analyze the program stored in the memory or transmitted on a bus, and thus preventing a behavior of the microprocessor system from being easily analyzed and understood by reading the program. Another aspect of the fifth object of the present invention relates to a randomized microprocessor system.
The above fifth object of the present invention is achieved by a microprocessor system including a microprocessor and a memory storing items accessed by the microprocessor. The microprocessor system comprises:
means provided between the microprocessor and the memory for differentiating a bit order of a first item processed by the microprocessor from that of a second item corresponding to the first item and stored in the memory.
A further aspect of the fifth object of the present invention relates to a method for randomizing a microprocessor system including a microprocessor and a memory storing a program executable by the microprocessor. The microprocessor system is randomized by inverting some bit values on a path from the microprocessor to the memory in order to make it difficult to read and analyze the program stored in the memory or transmitted on a bus, and thus prevent a behavior of the microprocessor system from being easily analyzed and understood by reading the program. Still a further aspect of the fifth object of the present invention relates to a randomized microprocessor system.
The above fifth object of the present invention is also achieved by a microprocessor system including a microprocessor and a memory storing items accessed by the microprocessor. The microprocessor system comprises:
means provided between the microprocessor and the memory for inverting some bit values of an intermediate item between a first item processed by the microprocessor and a second item corresponding to the first item and stored in the memory.
In the microprocessor system according to the present invention, the bit order is exchanged and/or the bit value is inverted for the intermediate item between the first items processed by the microprocessor and the second items stored in the memory. Therefore, it is difficult for outsiders to analyze and understand a behavior of the microprocessor system by directly reading the opcodes or contents stored in the memory or monitoring the data transmitted on a data bus. Advantageously, this improves a security for the microprocessor system, in particular, an IC card system.
It is a sixth object of the present invention to overcome the above-mentioned sixth disadvantage of the prior art. The sixth object of the present invention relates to the fact that a microprocessor system including bus lines is randomized such that it is difficult to analyze and understand data transmitted on the bus lines when the data is tapped at the bus lines.
The above sixth object of the present invention is achieved by a microprocessor system including a microprocessor, a memory storing items accessed by the microprocessor and a plurality of interconnection layers being connected to, on one hand, the microprocessor and, on the other hand, the memory and forming bus lines in columns and bus lines in rows, the bus lines arranged on the separate interconnection layers being connected to one another via through holes, characterized in that:
the bus lines in columns and the bus lines in rows are aligned in a random bit order with respect to a bit order of digital signals to be processed.
The through holes may be randomly arranged with respect to the bit order of the digital signals to be processed.
Thus, according to the present invention, since the bus lines are randomly aligned to the bit order of the digital signals to be processed and, as a result, the bits of the signals transmitted on the bus lines are not ordered in sequence, it is difficult to analyze the signals by reading the signals from the data bus.
Furthermore, in another aspect of the sixth object of the present invention, it is required that bus lines of a microprocessor system be protected from being directly contacted by some tools such as a manual probing unit.
This object is achieved by distributing at least a set of bus lines in columns or in rows over some interconnection layers. In this case, since all the bus lines of the set of the bus lines in columns or in rows are not always provided on the same interconnection layer, it is difficult to analyze or set the data on the bus lines by directly contacting the bus lines by means of the tool, for example, the manual probing device.
In a further aspect of the sixth object of the present invention, a metallic interconnection layer of a rectangular shape covers at least a portion of a region around the through hole. Thus, patterns formed on the interconnection layers are protected from being analyzed.